package Algorithm.interview;

/**
 * @Author self
 * @Date 2025/9/3 21:48
 * @Describe 中序遍历的下一个节点
 * 输入一个二叉树的节点，要求返回按中序遍历的顺序，输出输入节点的下一个节点。要求 O(1) 空间复杂度。
 *
 * 示例
 *        1
 *      /  \
 *    2     3
 *  /  \    /  \
 * 4    5   6    7
 *         /     /\
 *        8     9
 * 以上面的二叉树为例，
 * 输入节点 4，返回节点 2；
 * 输入节点 2 ，返回节点 5；
 * 输入节点 5，返回节点 1；
 * 输入节点 7，返回节点 null。
 */
public class InorderSuccessor {

    static class TreeLinkNode{
        int val;
        TreeLinkNode left;
        TreeLinkNode right;
        TreeLinkNode parent;

        TreeLinkNode(int val) {
            this.val = val;
        }
    }

    /**
     * 找到中序遍历中给定节点的下一个节点
     * 时间复杂度: O(h), h 是树高
     * 空间复杂度: O(1)
     *
     * @param p 当前节点
     * @return 中序后继节点，如果没有则返回 null
     */
    public static TreeLinkNode inorderSuccessor(TreeLinkNode p) {
        if (p == null) return null;

        // 情况 1: 有右子树 -> 找右子树中最左边的节点
        if (p.right != null) {
            TreeLinkNode node = p.right;
            while (node.left != null) {
                node = node.left;
            }
            return node;
        }

        // 情况 2: 没有右子树 -> 向上找第一个“左路径”的祖先
        TreeLinkNode parent = p.parent;
        TreeLinkNode child = p;

        while (parent != null && child == parent.right) {
            // 当前节点是父节点的右孩子，继续向上
            child = parent;
            parent = parent.parent;
        }

        // 此时 parent 就是中序后继
        // 如果 parent 为 null，说明 p 是最后一个节点
        return parent;
    }

    // --- 测试代码 ---
    public static void main(String[] args) {
        // 构建题目中的树
        TreeLinkNode root = new TreeLinkNode(1);
        TreeLinkNode node2 = new TreeLinkNode(2);
        TreeLinkNode node3 = new TreeLinkNode(3);
        TreeLinkNode node4 = new TreeLinkNode(4);
        TreeLinkNode node5 = new TreeLinkNode(5);
        TreeLinkNode node6 = new TreeLinkNode(6);
        TreeLinkNode node7 = new TreeLinkNode(7);
        TreeLinkNode node8 = new TreeLinkNode(8);
        TreeLinkNode node9 = new TreeLinkNode(9);

        root.left = node2;   root.right = node3;
        node2.parent = root; node3.parent = root;

        node2.left = node4;  node2.right = node5;
        node4.parent = node2; node5.parent = node2;

        node3.left = node6;  node3.right = node7;
        node6.parent = node3; node7.parent = node3;

        node6.left = node8;
        node8.parent = node6;

        node7.left = node9;
        node9.parent = node7;

        // 测试
        System.out.println(inorderSuccessor(node4).val); // 2
        System.out.println(inorderSuccessor(node2).val); // 5
        System.out.println(inorderSuccessor(node5).val); // 1
        System.out.println(inorderSuccessor(node7));     // null
    }
}
